//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 
//
// 示例 1： 
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
// 
//
// 示例 2： 
//
// 输入: "cbbd"
//输出: "bb"
// 
// Related Topics 字符串 动态规划 
// 👍 2802 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：最长回文子串
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P5_LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new P5_LongestPalindromicSubstring().new Solution();
        MyUtil.print(solution.longestPalindrome("bb"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 从i位置开始，以回文数为奇数或偶数的目标扩散，取最大值
     * T: O(N^2)
     * S: O(1)
     */
    class Solution {
        public String longestPalindrome(String str) {
            if (str == null) {
                return null;
            }
            if (str.length() == 1) {
                return str;
            }
            char[] cs = str.toCharArray();
            // 定义左右两边界
            int l, r;
            String res = "";
            for (int i = 1; i < cs.length; i++) {
                // 奇数扩散
                l = r = i;
                while (l >= 1 && r < cs.length - 1 && cs[l] == cs[r]) {
                    if (cs[l - 1] != cs[r + 1]) {
                        break;
                    }
                    l--;
                    r++;
                }
                // 奇数回文串
                String oddStr = new String(cs, l, r - l + 1);
                // 偶数扩散
                l = r = i;
                while (l >= 1 && r < cs.length && cs[l] == cs[r]) {
                    if (l == r) {
                        if (cs[l - 1] != cs[r]) {
                            break;
                        }
                        l--;
                    } else {
                        if (r + 1 < cs.length && cs[l - 1] == cs[r + 1]) {
                            l--;
                            r++;
                        } else {
                            break;
                        }

                    }
                }
                // 偶数回文串
                String evenStr = new String(cs, l, r - l + 1);
                // 取最长的
                String innerMaxStr = evenStr.length() > oddStr.length() ? evenStr : oddStr;
                res = innerMaxStr.length() > res.length() ? innerMaxStr : res;
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}